#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        priority_queue<int> pq;
        int ret = 0;
        for (auto i : nums)
        {
            ret += i;
            if (pq.size() < k) pq.push(i);
            else if (pq.top() > i) pq.pop(), pq.push(i);
        }
        priority_queue<int, vector<int>, greater<int>> pqg;
        for (int i = 0; i < k && i < nums.size(); i++) pqg.push(pq.top()), pq.pop();
        while (k--)
        {
            int tmp = pqg.top();
            ret = ret - tmp - tmp;
            pqg.pop();
            pqg.push(-tmp);
        }
        return ret;
    }
};